There has been known a Latin square fat-tree network as a network that connects multiple nodes (physical servers, for example) configured to perform collective communication. The Latin square fat-tree network is capable of connecting a larger quantity of nodes than an ordinary fat-tree network.
FIG. 1 illustrates an example of a Latin square fat-tree network. In the example of FIG. 1, a circle figure represents a node, a hatched square figure represents a spine switch, and an unhatched square figure represents a leaf switch. The quantity of ports on each switch is 6, and the number n, obtained by dividing the quantity of ports by 2, and then subtracting 1 from the resultant number, is 2. This number corresponds to the order of a finite projective plane. The quantity of nodes connected to the leaf switches is 21.
FIG. 2 illustrates an ordinary fat-tree network using the same switches as used in FIG. 1. In the example of FIG. 2, the quantity of nodes connected to the leaf switches is 9, which is smaller than in the example of FIG. 1.
FIG. 3 illustrates another example of a Latin square fat-tree network. In the example of FIG. 3, the number of ports on each switch is 8, and the number n is 3. The number of nodes connected to the leaf switches is 52.
FIG. 4 illustrates an ordinary fat-tree network using the same switches as used in FIG. 3. In the example of FIG. 4, the number of nodes connected to the leaf switches is 16, which is smaller than in the example of FIG. 3.
There has been known a technique for an ordinary fat-tree network to perform all-to-all communication (all-to-all communication is a kind of collective communication) in which all nodes participate. However, there has not been known a technique for a Latin square fat-tree network to perform all-to-all communication in which all nodes participate.
The related techniques are described in, for example, Japanese Laid-open Patent Publication Nos. 2014-164756 and 2013-25505, as well as M. Valerio, L. E. Moser and P. M. Melliar-Smith, “Recursively Scalable Fat-Trees as Interconnection Networks”, IEEE 13th Annual International Phoenix Conference on Computers and Communications, 1994.